1486E - Paired Payment - CodeForces Solution

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
const int inf = 1e9 + 100;
const ll linf = 1e18 + 100;
const int N = 1e5;

template <typename T>
bool umx(T &a, T b) {
    return (b > a) ? (a = b, 1) : 0;
}

template <typename T>
bool umn(T &a, T b) {
    return (b < a) ? (a = b, 1) : 0;
}

vector <vector <pair<int, int>>> g;
vector <map<int, int>> g1;
vector <int> met;
void dfs_build(int v) {
    met[v] = 1;
    for (auto [u, w] : g[v]) {
        if (u == v) continue;
        if (!met[u]) {
            dfs_build(u);
        }
        for (auto [u1, w1] : g[u]) {
            if (u1 == v) continue;
            int cost = (w1 + w) * (w1 + w);
            if (g1[v].find(u1) == g1[v].end()) {
                g1[v][u1] = cost;
                g1[u1][v] = cost;
            } else {
                umn(g1[v][u1], cost);
                umn(g1[u1][v], cost);
            }
        }
    }
}


int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);

    int n, m;
    cin >> n >> m;
    g.resize(n + 1), g1.resize(n + 1), met.resize(n + 1);

    for (int i = 0; i < m; i++) {
        int x, y, w;
        cin >> x >> y >> w;
        g[x].push_back({y, w});
        g[y].push_back({x, w});
    }



    vector <int> len(n + 1, inf);
    len[1] = 0;
    set <pair<int, pair<int, int>>> t;
    t.insert({0, {0, 1}});
    for (int i = 2; i <= n; i++) {
        t.insert({inf, {0, i}});
    }

    while((int)t.size() > 0) {
        auto x = *t.begin();
        t.erase(x);
//        cout << x.first << " " << x.second.first << " " << x.second.second << "\n";

        for (auto [u, w] : g[x.second.second]) {
            if (x.second.first > 0) {
                int cost = x.first + (x.second.first + w) * (x.second.first + w);
                if (len[u] > cost) {
                    t.erase({len[u], {0, u}});
                    len[u] = cost;
                    t.insert({len[u], {0, u}});
                }
            } else {
                    t.insert({x.first, {w, u}});
            }
        }
    }

    for (int i = 1; i <= n; i++) {
        if (len[i] == inf) cout << "-1 ";
         else cout << len[i] << " ";
    }
}